package main

//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//
//
//
// 示例：
//
// 输入：1->2->4, 1->3->4
//输出：1->1->2->3->4->4
//
// Related Topics 递归 链表
// 👍 1461 👎 0

//leetcode submit region begin(Prohibit modification and deletion)

type ListNode struct {
	Val  int
	Next *ListNode
}


func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{
		Val:  0,
		Next: nil,
	}
	tail := head
	for l1 != nil || l2 != nil {
		node := &ListNode{
			Val:  0,
			Next: nil,
		}
		if l1 == nil && l2 != nil  {
			node.Val = l2.Val
			l2 = l2.Next
		} else if l1 != nil && l2 == nil {
			node.Val = l1.Val
			l1 = l1.Next
		} else if l1.Val > l2.Val {
			node.Val = l2.Val
			l2 = l2.Next
		} else {
			node.Val = l1.Val
			l1 = l1.Next
		}

		tail.Next = node
		tail = tail.Next
	}

	return head.Next
}


func main() {

}
